#pragma once
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

//红黑树变化口诀：看叔叔
//重点：1.一棵树复用的set和map，利用KV结构的V保存pair或key，K保存K，供个别函数传参使用
//      （怎么封装：KV结构，封装后怎么比较：仿函数获取里面元素:key返回key,pair返回里面的key）
//2.迭代器的封装，中序的非递归方法二，方法一是栈实现的
//3.补充其他函数，如operator[]，默认成员函数的实现，find的实现等


enum Color { RED,BLACK};//枚举类型：用数字代表一种颜色，如同用数字代表商品（等同商品价格），方便使用

template <class T>//采用的是K和T，T可以是k，也可以是其他结构pair
struct RB_TreeNode
{

	RB_TreeNode* _left;
	RB_TreeNode* _right;
	RB_TreeNode* _parent;
	T _data;
	Color _col;

	RB_TreeNode(const T& data)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(data)
		,_col(RED)//颜色默认用红色，因为根节点是黑色，且插入黑色一定会影响黑节点数量这一规则，插入红色只是可能影响连续红色这一规则
	{}
};

//实现红黑树迭代器
template <class T, class Ref, class Ptr>
struct RB_Tree_iterator
{
	typedef RB_TreeNode<T> Node;//T不能是const，这是匹配两个Node用的
	typedef RB_Tree_iterator<T, Ref, Ptr> self;

	Node* _node;
	RB_Tree_iterator(Node* node)
		:_node(node)
	{}

	Ref operator*()
	{
		return _node->_data;
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	bool operator!=(const self& it)
	{
		return this->_node != it._node;
	}

	self& operator++()
	{
		//++,是中序遍历的后一个，即若是用stack实现遍历的话也可以，但是比较麻烦了，对于三叉树来说可以直接判断的
		if (this->_node->_right)
		{
			//该节点右子树不为空，下一个就是右子树的最左节点
			Node* cur = this->_node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			this->_node = cur;
		}
		else
		{
			//该节点的右子树为空，说明已经走到这颗子树的最后了，得回去找祖先，找到孩子是父亲的左节点，这个父亲就是下一个
			//因为中序是左中右，若是这个祖先是某个节点的左，那么下一个就是这某个节点，因为左中右的缘故
			Node* child = this->_node;
			Node* parent = child->_parent;
			while (parent && child == parent->_right)//parent不存在说明就是根了。根就到end了返回空就行，因为这实现的是无哨兵的
			{
				child = parent;
				parent = child->_parent;
			}

			this->_node = parent;//空也是赋值
		}
		return *this;
	}

	//后置++
	self operator++(int)
	{
		self temp = *this;
		if (this->_node->_right)
		{
			//该节点右子树不为空，下一个就是右子树的最左节点
			Node* cur = this->_node->_right;
			while (cur->_left)
			{
				cur = cur->_left;
			}
			this->_node = cur;
		}
		else
		{
			Node* child = this->_node;
			Node* parent = child->_parent;
			while (parent && child == parent->_right)
			{
				child = parent;
				parent = child->_parent;
			}

			this->_node = parent;//空也是赋值
		}
		return temp;
	}

	self& operator--()
	{
		//--是++的反过来，看其左节点就行
		if (this->_node->_left)
		{
			//左节点不为空，说明其左树已经访问完了，左树的最右边的节点就是其上一个节点
			Node* cur = this->_node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			this->_node = cur;
		}
		else
		{
			//左节点为空，说明前一个节点是你的祖先，找到孩子是父亲的右节点，该父亲就是上一个节点。
			//因为中序是左中右，某个祖先节点右子树的最左节点就是现在的这个节点，找回他祖先就行
			Node* child = this->_node;
			Node* parent = child->_parent;
			while (parent && child == parent->_left)
			{
				child = parent;
				parent = child->_parent;
			}
			this->_node = parent;
		}
		return *this;
	}

	self operator--(int)//后置--
	{
		//--是++的反过来，看其左节点就行
		self temp = *this;
		if (this->_node->_left)
		{
			Node* cur = this->_node->_left;
			while (cur->_right)
			{
				cur = cur->_right;
			}
			this->_node = cur;
		}
		else
		{

			Node* child = this->_node;
			Node* parent = child->_parent;
			while (parent && child == parent->_left)
			{
				child = parent;
				parent = child->_parent;
			}
			this->_node = parent;
		}
		return temp;
	}


};



//如何用一棵红黑树复用set和map，统一用kv结构
//set RE_Tree<K,K>
//map RB_Tree<K,pair<K,V>>
//那第一个模板参数能否去掉？不可以的，因为实现map和set的个别函数如find等函数，传的只能是Key，set可以省略第一个，map能省略吗？明显不能抽取类型里面的类型


//koft的是外面传进来的仿函数，通过这个类型获得里面需要比较的东西
//要写成泛型变成，key能直接比较，pair比较的确实里面的key（这能强转吗？不能，只能写死成data.first），故通过仿函数这个类型泛型编程


template <class K,class T ,class KofT>//还可多设立一个比较仿函数控制方向
class RB_Tree
{
	typedef RB_TreeNode<T> Node;
	void InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		InOrder(root->_left);
		cout << root->_value << " ";
		InOrder(root->_right);
	}

	Node* CopyTree(Node* root,Node* parent)
	{
		//前序遍历生成树
		if (root == nullptr)
			return nullptr;
		Node* newNode = new Node(root->_data);
		newNode->_parent = parent;
		//if (_root == nullptr)//不应该直接用_root进行修改，因为_root是直接关联这个树的，下面修改也会导致_root的左右一直更换
		//	_root = newNode;
		//_root->_left = CopyTree(root->_left);
		//_root->_right = CopyTree(root->_right);
		newNode->_left = CopyTree(root->_left,newNode);
		newNode->_right = CopyTree(root->_right,newNode);
		return newNode;
	}

	void destoryTree(Node* root)
	{
		if (root == nullptr)
			return;
		destoryTree(root->_left);
		destoryTree(root->_right);
		delete root;

	}
public:
	typedef RB_Tree_iterator<T, T&, T*> iterator;
	typedef RB_Tree_iterator<T, const T&, const T*> const_iterator;

	//构造用默认
	RB_Tree() = default;
	RB_Tree(const RB_Tree<K, T, KofT>& t)
	{
		_root = CopyTree(t._root,nullptr);
	}
	//赋值运算符重载
	RB_Tree< K, T, KofT >& operator=(RB_Tree<K, T, KofT> t)
	{
		//拷贝后判断两个是否一样，不然就两次析构了
		swap(_root, t._root);
		return *this;
	}

	//析构
	~RB_Tree()
	{
		//后序析构
		destoryTree(_root);
		_root = nullptr;
	}

	pair<iterator,bool> insert(const T& data)
	{
		Node* cur = _root;
		Node* parent = nullptr;
		KofT kot;
		Node* tmp = nullptr;
		if (_root == nullptr)
		{
			_root = new Node(data);
			_root->_col = BLACK;
			return make_pair(iterator(_root),true);
		}
		else
		{
			while (cur)//按搜索树方法寻找，找到是空就插入
			{
				if (kot(data) > kot(cur->_data))
				{
					parent = cur;
					cur = cur->_right;
				}
				else if (kot(data) < kot(cur->_data))//利用传进来的仿函数获取里面的值比较
				{
					parent = cur;
					cur = cur->_left;
				}
				else
					return make_pair(iterator(cur), false);//相同先不考虑
			}

			cur = new Node(data);
			tmp = cur;//保存新建的节点，因为后面cur会变
			cur->_col = RED;
			cur->_parent = parent;
			if (kot(data)> kot(parent->_data))
				parent->_right = cur;
			else
				parent->_left = cur;
		}


		while (parent && parent->_col == RED)
		{
			//parent是红色说明上面的节点必然是黑，因为插入之前肯定是红黑树了

			//先分左右子树,用于区分左右旋转
					//弄好亲戚关系
			Node* grandfather = parent->_parent;
			Node* uncle = grandfather->_left;
			if (parent == grandfather->_left)
			{
				uncle = grandfather->_right;
			}

			//进入情况
			if (grandfather->_left == parent)
			{
				//情况一
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else//叔叔为空，或叔叔存在且为黑
				{
					//情况二：连续左，右单旋
					if (cur == parent->_left)
					{
						RotateR(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
						
					}
					//情况三：折线，左右双旋
					else
					{
						RotateL(parent);
						RotateR(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;

				}
			}
			else
			{
				//情况一
				if (uncle && uncle->_col == RED)
				{
					uncle->_col = parent->_col = BLACK;
					grandfather->_col = RED;

					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//情况二：连续右，左单旋
					if (parent->_right == cur)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					//情况三：折线，右左双旋
					else
					{
						RotateR(parent);
						RotateL(grandfather);

						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}//while
		_root->_col = BLACK;//循环结束，强制写死
		return make_pair(iterator(tmp), true);
	}


	iterator Begin()
	{
		//返回最左节点
		Node* cur = _root;
		while (_root && cur->_left)
		{
			cur = cur->_left;
		}
		return iterator(cur);
	}
	iterator End()
	{
		return nullptr;
	}

	const_iterator Begin() const 
	{
		//返回最左节点
		Node* cur = _root;
		while (_root && cur->_left)
		{
			cur = cur->_left;
		}
		return const_iterator(cur);
	}
	const_iterator End() const 
	{
		return nullptr;
	}

	iterator Find(const K& key)
	{
		KofT kot;
		Node* cur = _root;
		while (cur)
		{
			if (key > kot(_root->_data))
				cur = cur->_right;
			else if (key < kot(_root->_data))
				cur = cur->_left;
			else
				return iterator(cur);
		}
		return End();

	}
private:
	Node* _root = nullptr;

	void RotateL(Node* parent)//旋转只关乎父子,1.子树左节点是否为空，2.旋转的parent是否是根(且根无父)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		Node* ppNode = parent->_parent;

		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}

		subR->_left = parent;
		parent->_parent = subR;
		if (_root == parent)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subR;
			else
				ppNode->_right = subR;
			subR->_parent = ppNode;
		}

	}
	void RotateR(Node* parent)//旋转只关乎父子,1.子树左节点是否为空，2.旋转的parent是否是根（且根无父）
	{
		Node* ppNode = parent->_parent;
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		subL->_right = parent;
		parent->_parent = subL;
		if (_root == parent)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
				ppNode->_left = subL;
			else
				ppNode->_right = subL;

			subL->_parent = ppNode;
		}
	}

	
};

